{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原始文本，文本长度 200\n",
      "zhonghaoweizuishuaizhonghaoweizauishuaizhonghaoweizhonghaoweizuishuaizhonghaoweizauishuaizhonghaoweizhonghaoweizuishuaizhonghaoweizauishuaizhonghaoweizhonghaoweizuishuaizhonghaoweizauishuaizhonghaowei\n",
      "压缩编码，编码长度 79\n",
      "2681514781152359262191982113728303234362613941434529313335564759505342442757486051655568624961587738406678705052827446797190853773679363378754976999\n",
      "解压解码，压缩比率 60.50%\n",
      "zhonghaoweizuishuaizhonghaoweizauishuaizhonghaoweizhonghaoweizuishuaizhonghaoweizauishuaizhonghaoweizhonghaoweizuishuaizhonghaoweizauishuaizhonghaoweizhonghaoweizuishuaizhonghaoweizauishuaizhonghaowei"
     ]
    }
   ],
   "source": [
    "#include <stdio.h>\n",
    "#include <stdlib.h>\n",
    "#include <string.h>\n",
    "\n",
    "#define NOT_EXIST -1\n",
    "\n",
    "// 字典结构\n",
    "typedef struct{\n",
    "    char** seq;\n",
    "    int* code;\n",
    "    int size;\n",
    "    int max_size;\n",
    "}Dictionary;\n",
    "\n",
    "//插入字典\n",
    "void insert_seq(Dictionary* dict, char* seq){\n",
    "    int i = dict->size;\n",
    "    // 分配字符串空间\n",
    "    dict->seq[i] = malloc(sizeof(char) * strlen(seq) + 1);\n",
    "    dict->code[i] = i;\n",
    "    dict->size++;\n",
    "    // 将字符串加入分配的空间\n",
    "    strcpy(dict->seq[i], seq);\n",
    "}\n",
    "\n",
    "void init_dictionary(Dictionary* dict, int max_size){\n",
    "    dict->max_size = max_size;\n",
    "    dict->size = 0;\n",
    "    // 分配初始字符串数组空间\n",
    "    dict->seq = malloc(sizeof(char *) * max_size);\n",
    "    dict->code = malloc(sizeof(int) * max_size);\n",
    "    insert_seq(dict, \"#\");\n",
    "    // 初始字符串\n",
    "    char seq[2] = \"a\";\n",
    "    //插入26个字母至索引表 \n",
    "    for(int i = 0;i < 26;i++){\n",
    "        insert_seq(dict,seq);\n",
    "        seq[0]++;\n",
    "    }\n",
    "}\n",
    "\n",
    "int get_seq_code(Dictionary* dict,char* seq){\n",
    "    // 顺序查找\n",
    "    // todo:也许以后可以改进为二分查找，或者其他查找方式，这里为了简单就顺序查找咯\n",
    "    for(int i=0;i<dict->size;i++){\n",
    "        if(strcmp(dict->seq[i], seq) == 0){\n",
    "            return dict->code[i];\n",
    "        }\n",
    "    }\n",
    "    return NOT_EXIST;\n",
    "}\n",
    "\n",
    "char* get_code_seq(Dictionary* dict, int code){\n",
    "    if (code < 0 || code >= dict->size){\n",
    "        return NULL;\n",
    "    }else{\n",
    "        return dict->seq[code];\n",
    "    }\n",
    "    \n",
    "}\n",
    "\n",
    "void lzw_encode(char* text, Dictionary* dict){\n",
    "    FILE* pFile;\n",
    "    char current[1000];\n",
    "    char next;\n",
    "    int code;\n",
    "    int i = 0;\n",
    "//     if((pFile = fopen (\"./codes\", \"wb\"))==NULL)\n",
    "//     {\n",
    "//         printf(\"cant open the file\");\n",
    "//         exit(0);\n",
    "//     }\n",
    "    while(i < strlen(text)){\n",
    "        sprintf(current, \"%c\", text[i]);\n",
    "        next = text[i+1];\n",
    "//         if(next=='\\0'){\n",
    "//            return;\n",
    "//         }\n",
    "        while(get_seq_code(dict,current) != NOT_EXIST){\n",
    "            sprintf(current,\"%s%c\",current,next);\n",
    "            i++;\n",
    "            next = text[i+1];\n",
    "            \n",
    "        }  \n",
    "        //多了一个next字符，需要抹掉\n",
    "        current[strlen(current)-1] = '\\0';\n",
    "        //倒回一个位\n",
    "        next = text[i]; \n",
    "        code = get_seq_code(dict,current);\n",
    "        // 插入新的字符组合\n",
    "        sprintf(current,\"%s%c\",current,next);\n",
    "        insert_seq(dict,current);\n",
    "        printf(\"%d\",code);\n",
    "        //fwrite(&code,sizeof(int),1,pFile);\n",
    "    }\n",
    "//     fclose (pFile);\n",
    "//     free(pFile);\n",
    "}\n",
    "\n",
    "\n",
    "void lzw_decode(int codes[],int n,Dictionary* dict){\n",
    "    int code;\n",
    "    char pre[1000];\n",
    "    char* output;\n",
    "    code = codes[0];\n",
    "    output = get_code_seq(dict,code);\n",
    "    int i;\n",
    "    printf(\"%s\",output);\n",
    "    for(i=1;i<n;i++){\n",
    "        code = codes[i];\n",
    "        strcpy(pre,output);\n",
    "        output = get_code_seq(dict,code);\n",
    "        sprintf(pre,\"%s%c\",pre,output[0]);\n",
    "        insert_seq(dict,pre);\n",
    "        printf(\"%s\",output);\n",
    "    }\n",
    "}\n",
    "\n",
    "void print_dictionart(Dictionary* dict){\n",
    "    printf(\"===========================\\n\");\n",
    "    printf(\"  Code            Sequence\\n\");\n",
    "    printf(\"===========================\\n\");\n",
    "    for(int i=0;i<dict->size;i++){\n",
    "        printf(\"%4d%16c\",dict->code[i],' ');\n",
    "        printf(\"%s\\n\",dict->seq[i]);\n",
    "    }\n",
    "    printf(\"===========================\\n\");\n",
    "}\n",
    "\n",
    "int* read_code(char* file){\n",
    "    FILE * fp;\n",
    "    // TO-DO\n",
    "    int buffer[1000];\n",
    "    if((fp=fopen(\"codes\",\"rb\"))==NULL)\n",
    "    {\n",
    "        printf(\"cant open the file\");\n",
    "        exit(0);\n",
    "    }\n",
    "    fread(buffer,sizeof(int),1000,fp);\n",
    "    int i =0;\n",
    "    for(;i<1000;i++){\n",
    "        printf(\"%d\",buffer[i]);\n",
    "    }\n",
    "    return NULL;\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "    Dictionary dict;\n",
    "    Dictionary dict_decode;\n",
    "    init_dictionary(&dict, 1000);\n",
    "    init_dictionary(&dict_decode,1000);\n",
    "//     print_dictionart(&dict);\n",
    "//     printf(\"%d\",get_seq_code(&dict,\"D\"));\n",
    "    char * text = \"zhonghaoweizuishuaizhonghaoweizauishuaizhonghaoweizhonghaoweizuishuaizhonghaoweizauishuaizhonghaoweizhonghaoweizuishuaizhonghaoweizauishuaizhonghaoweizhonghaoweizuishuaizhonghaoweizauishuaizhonghaowei\";\n",
    "    printf(\"原始文本，文本长度 %d\\n\",strlen(text));\n",
    "    printf(\"%s\\n\",text);\n",
    "    int codes[] = {26,8,15,14,7,8,1,15,23,5,9,26,21,9,19,8,21,1,37,28,30,32,34,36,26,1,39,41,43,45,29,31,33,35,56,47,59,50,53,42,44,27,57,48,60,51,65,55,68,62,49,61,58,77,38,40,66,78,70,50,52,82,74,46,79,71,90,85,37,73,67,93,63,37,87,54,97,69,99};\n",
    "    int n = (sizeof(codes)/sizeof(codes[0]));\n",
    "    printf(\"压缩编码，编码长度 %d\\n\",n);\n",
    "    lzw_encode(text,&dict);\n",
    "    //print_dictionart(&dict);\n",
    "    float radio = 1-1.0*n/(strlen(text));\n",
    "    printf(\"\\n解压解码，压缩比率 %.2f\\%\\n\",radio*100);\n",
    "    lzw_decode(codes,n,&dict_decode);\n",
    "    return 0;\n",
    "}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C",
   "language": "c",
   "name": "c"
  },
  "language_info": {
   "file_extension": ".c",
   "mimetype": "text/plain",
   "name": "c"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
